package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * Description 基数排序
 *
 * @ClassName algorithm.sort.RadixSort
 * @Version 1.0
 * @Date: 2022/2/19 16:32
 * @Author xuyi
 */
public class RadixSort {

    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2,56,33,87,89,25,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        int maxBit = getMaxBit(arr);
        radixSort(arr,maxBit);
    }

    private int getMaxBit(int[] arr){
        int max = getMax(arr);
        return getLength(max);
    }

    private int getLength(int num){
        if(num==0){
            return 1;
        }
        int len = 0;
        for(int tmp=num;tmp!=0;tmp/=10){
            len++;
        }
        return len;
    }

    private int getMax(int[] arr){
        int max = arr[0];
        for(int i =1;i<arr.length;i++){
            if(arr[i]>max){
                max = arr[i];
            }
        }
        return max;
    }

    private void radixSort(int[] arr,int maxBit){
        int mod = 10;
        int dev = 1;
        for(int i=0;i<maxBit;i++,mod*=10,dev*=10){
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] buckets = new int[mod*2][0];
            for(int j=0;j<arr.length;j++){
                int bucket = (arr[j]%mod)+mod;
                buckets[bucket] = arrAppend(buckets[bucket],arr[j]);
            }
            int pos = 0;
            for(int[] bucket:buckets){
                for(int num:bucket){
                    arr[pos++] = num;
                }
            }
        }
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}
